1. Field of the Invention
The present invention relates, generally, to network routing and scheduling, and more particularly, to the computation of capacity, and algorithms to achieve capacity, in multi-channel, multi-radio (e.g., wireless) mesh networks.
2. Description of the Related Art
The emergence of broadband wireless networks has been spurred by the development of standards such as IEEE 802.11 a/b/g and 802.16. These networks are being deployed as a solution to extending the reach of the last-mile access to the Internet, using a multi-hop configuration. In multi-hop networks, communication between two end nodes is carried out through a number of intermediate nodes whose function is to relay information from one point to another. Many such networks are already in use, ranging from prototype testbeds to complete commercial solutions. As shown in FIG. 1, one popular deployment method is to use one standard, such as IEEE 802.16, for intercell communications, i.e., back-hauling traffic on the multi-hop wireless relay backbone, while using another standard, such as 802.11 a/b/g, for intracell communications, i.e., to carry traffic over the last hop to the user. This isolates traffic on the wireless backbone from the fluctuating load and interference from the last-hop end users.
Fixed multi-channel, multi-hop wireless networks with multiple radios per node are referred to as MC-MR networks. Such MC-MR networks typically have the following characteristics:
1. There are multiple wireless channels of operation, and these channels are orthogonal to each other.
2. Nodes have multiple radio transceivers, which allow them to communicate, interference-free and simultaneously, with more than one neighbor at the same time using different channels.
3. Full-duplex operation is possible at each node, i.e., a node can be receiving from or transmitting to a neighbor i on channel A, while transmitting to or receiving from neighbor j on channel B, where A≠B.
4. The number of orthogonal wireless channels could be limited in number, which implies that more than one node in a given region could contend for the same channel at the same time, thereby resulting in interference and collisions.
5. The radios (also referred to as Network Interface Cards, or NICs) at each node are capable of fast switching between channels, with a switching overhead. Channels can be assigned for communication between neighbors in a static or dynamic fashion. In a static link-channel assignment, every link between a pair of neighboring nodes is bound to a particular channel, and this binding does not vary over time. In dynamic link-channel assignment, the bindings between a link and the operating channel for that link can vary dynamically with time. While dynamic assignment involves negotiation, it also provides more flexibility to combat interference.
One of the main goals in the design of fixed wireless broadband networks is capacity planning. Within this realm, given a set of end-to-end demands, there are multiple design goals for which a network can be optimized, e.g., maximizing a function of the rates where the function can be chosen to be a user utility function or a network price function, ensuring some notion of rate fairness, or minimizing end-to-end delays. Every design goal involves designing routes, assigning channels, and scheduling packets to meet such goals. Numerous studies have considered routing, channel assignment, and scheduling for such networks. Some have studied the problem of finding efficient routes to maximize throughput, some have considered only channel assignment and scheduling, and others have considered both routing and scheduling. However, all of these previous studies considered only a subset of the problem, e.g., addressing only the question of how to improve throughput compared to other known algorithms.